/**
 * 给定衣蛾数组A以及一个整数target
 * 如果A的某个子数组中，target的数量严格大于该子数组长度的一半，则是符合条件的
 * 求符合条件的子数组的数量
 * 
 * 考虑一个前缀和数组S，S[i]表明A[1..i]中target的数量
 * 则A[i..j]如果符合条件需要满足：
 * 2 * (Sj - S[i - 1]) > j - (i - 1)
 * 移项得到
 * 2Sj - j > 2S[i-1] - (i - 1)
 * 令 Fx = 2Sx - x
 * 则原题目等价于问
 * for x in [0...N]: 
 *     for y in [x + 1...N]:
 *         比Fx大的Fy的数量
 * 求出F之后，这是一个标准的树状数组的用法  
 */
struct FenwickTree{ // 树状数组

using value_type = long long int;
using vec_type = vector<value_type>;

int n;
vec_type c;

FenwickTree() = default;

static int lowbit(int x){return x & -x;}

void init(int nn){this->c.assign((this->n=nn) + 1, 0);}

void modify(int pos, value_type delta){
    for(int i=pos;i<=this->n;i+=lowbit(i)) this->c[i] += delta;
}

value_type query(int pos)const{
    value_type ans = 0;
    for(int i=pos;i;i-=lowbit(i)) ans += this->c[i];
    return ans;
}

value_type query(int s, int e)const{return this->query(e) - this->query(s - 1);}

};


using vi = vector<int>;
using llt = long long;
llt const MOD = 1E9 + 7;
llt const None = 0x7F2F3F4F;

int N;
vi S;
vi F;
vi W;
FenwickTree Bt;

class Solution {
public:
    long long countMajoritySubarrays(vector<int>& nums, int target) {
        N = nums.size();
        nums.insert(nums.begin(), 0);
        S.assign(N + 1, 0);
        F.assign(N + 1, 0);
        for(int i=1;i<=N;++i){
            S[i] = target == nums[i] ? S[i - 1] + 1: S[i - 1];
            F[i] = S[i] + S[i] - i;
        }    
        
        W.assign(F.begin(), F.end());
        W.emplace_back(-2E9);
        sort(W.begin(), W.end());
        W.erase(unique(W.begin(), W.end()), W.end());

        int n = W.size();
        Bt.init(n);
        llt ans = 0;
        for(int i=N;i>=0;--i){
            auto c = lower_bound(W.begin(), W.end(), F[i]) - W.begin();
            ans += Bt.query(c + 1, n);
            Bt.modify(c, 1);
        }
        return ans;
    }
};
